﻿#pragma once

#include "Generation/Engine/Core/VecSet.h"

class FStage;

template<typename T>
class BucketQueue
{
private:
	TArray<TArray<T>*>* m_Buckets;

	private:
	//筒子的最低板
	int m_BucketMin;

	void Reset()
	{
		m_Buckets->Empty();
	}
	
public:
	BucketQueue()
	{
		m_Buckets = new TArray<TArray<T>*>();
	}

	void Add(T value, int cost)
	{
		// 先要知道当前桶队列中，最短的短板是哪个，是新来的还是老的。
		m_BucketMin = FMath::Min(m_BucketMin, cost);
	
		// 根据cost的最大值及历史最大值，决定 m_Buckets 的数量。
		// 而 m_BucketMin 的位置，是最小的有值的地方。
		// Grow the bucket array if needed.
		int distance = cost + 1 - m_Buckets->Num();
		while (distance > 0)
		{
			m_Buckets->Emplace(nullptr);
			--distance;
		}
	
		// 往这个相同优先级的队列中加入 value
		// Find the bucket, or create it if needed.
		auto bucket = (*m_Buckets)[cost];
		if (bucket == nullptr)
		{
			bucket = new TArray<T>();
			(*m_Buckets)[cost] = bucket;
		}
	
		bucket->Push(value);
	}
	
	T* RemoveNext()
	{
		// Advance past any empty buckets.
		// 满足两点才会加：1.m_BucketMin比总长度小 2.m_BucketMin位置是空的，那么加
		while (m_BucketMin < m_Buckets->Num() &&
			   ((*m_Buckets)[m_BucketMin] == nullptr || (*m_Buckets)[m_BucketMin]->Num() == 0))
		{
			m_BucketMin++;
		}
	
		// If we ran out of buckets, the queue is empty.
		// 过了，直接返回
		if (m_BucketMin >= m_Buckets->Num())
		{
			//Debug.LogError("有错误！！越界");
			return nullptr;
		}

		auto t = ((*m_Buckets)[m_BucketMin])->Pop();
		out2 = (&t);
		return out2;
	}
	T* out2;
	
	// T RemoveNext()
	// {
	// 	// Advance past any empty buckets.
	// 	// 满足两点才会加：1.m_BucketMin比总长度小 2.m_BucketMin位置是空的，那么加
	// 	while (m_BucketMin < m_Buckets->Num() &&
	// 		   ((*m_Buckets)[m_BucketMin] == nullptr || (*m_Buckets)[m_BucketMin]->Num() == 0))
	// 	{
	// 		m_BucketMin++;
	// 	}
	// 	
	// 	// If we ran out of buckets, the queue is empty.
	// 	// 过了，直接返回
	// 	if (m_BucketMin >= m_Buckets->Num())
	// 	{
	// 		//Debug.LogError("有错误！！越界");
	// 		return T();
	// 	}
	// 	
	// 	auto t = ((*m_Buckets)[m_BucketMin])->Pop();
	// 	return t;
	// }
};

class FReachability
{
public:
	constexpr static int m_Unknown = -2;
	constexpr static int m_Unreachable = -1;

	FArray2D<int>* m_Distances;
	FVecSet* m_Affected;
	int m_ReachedOpenCount = 0;

	FStage* stage;

	FArray2D<int> Distances()
	{
		return *m_Distances;
	}

	FReachability(FStage* stage);

	void SetDistance(FVec pos, int distance);

	void ClearDistance(bool force = false) const;

	void Process(TArray<FVec>* starting);


private:
	class FillStep
	{
	public:
		FVec pos;
		int distance;

		FillStep(FVec pos, int distance);
	};
};
